\section{Problema 3}

\subsection{Introducci\'on}

En el problema 3 debíamos encontrar un camino entre 2 piedras sobre un tronco de manera que un sapo dado pudiera recorrer. Aunque pareciera trivial, no lo es ya que el sapo tiene una cota mínima y máxima de distancia de salto.
Por cada instancia recibíamos dos enteros, \textit{p} y \textit{q} que nos indicaban exactamente eso. Además, sabíamos que ambos eran menores a \textbf{10}, por lo que sabíamos que la distancia que pudiera saltar el sapo era acotada por arriba y por abajo. \\


\subsection{Pseudoc\'odigo}
En el archivo \textbf{Ej3.java} podremos encontrar la clase ``Ej3'' con todas las funciones aqu\'i especificadas con pseudoc\'odigo (en el archivo hay m\'as funciones para acomodar cosas que no supusimos relevantes para el pseudocódigo). \\
Las funciones más interesantes son \textbf{existe\_camino} que es la función recursiva que devuelve el camino si existe y \textbf{buscar\_alcanzables} en la cual generamos un vector con información sobre qué piedras son alcanzables por cada piedra. \\
La función \textbf{es\_alcanzable} revisa, dados un entero \texttt{X} y un entero \texttt{Y} y \texttt{p} y \texttt{q}, si la distancia entre \texttt{X} y \texttt{Y} está en el rango predispuesto por \texttt{p} y \texttt{q}. \\

\begin{parr}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algorithm}[H]
\caption{\operL{algoritmo\_ppal}{ \vin{v\_p}{Vector$<$posicion$>$},\vin{p}{cota},\vin{q}{cota}, \vin{x}{posicion}, \vin{y}{posicion}}{String}}
\begin{algorithmic}[1]\parskip=1mm
\STATE tronco $\leftarrow$ buscar\_alcanzables(v\_p)
\STATE \textbf{var} res $\leftarrow$ lista vacía
\IF{existe\_camino(tronco, x, y, res)}
	\STATE return res
\ELSE 
	\STATE return `` ''
\ENDIF
\end{algorithmic}
\end{algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algorithm}[H]
\caption{\operL{existe\_camino}{ \vin{tronco}{Vector$<$posicion, alcanzables$>$}, \vin{x}{posicion}, \vin{y}{posicion}, \vin{res}{lista$<$posicion$>$}}{Boolean}}
\begin{algorithmic}[1]\parskip=1mm
\IF{(es\_alcanzable(x,y))}
	\STATE res = \{X,Y\}
	\STATE return TRUE
\ELSE
	\FOR{(todos los elementos X$_i$ pertenecientes a tronco$[$x$]$.alcanzables)}
		\IF{((No busqué desde X$_i$ todavía) y (no lo estoy recorriendo en esta recursión))}
			\STATE marcar como que lo estoy recorriendo al X$_i$
			\IF{($¬$(existe\_camino(tronco,X$_i$,Y,res))}
				\STATE marcar como ya visto el X$_i$
			\ELSE
				\STATE res = X + res,
				\STATE return TRUE				
			\ENDIF		
		\ENDIF
	\ENDFOR
	\STATE \COMMENT{si ya recorrí todos los alcanzables y no conseguí solución entonces no existe solución}
	\STATE return FALSE
\ENDIF
\end{algorithmic}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algorithm}[H]
\caption{\operL{buscar\_alcanzables}{ \vin{v\_p}{Vector$<$posicion$>$}}{Vector$<$posicion, alcanzables$>$}}
\begin{algorithmic}[1]\parskip=1mm
\STATE \textbf{var} tronco $\leftarrow$ vector vacío
\FOR{(todos los elementos v$_i$ de v\_p)}
	\STATE \textbf{var} lista\_alcanzables $\leftarrow$ lista vacía 
	\STATE \textbf{var} terminé $\leftarrow$ FALSE
	\STATE \COMMENT{primero busco los alcanzables desde la izquierda}
	\WHILE{((hay una piedra anterior) y !(terminé))}
		\IF{(es\_alcanzable(piedra\_anterior, v$_i$))}
			\STATE agregar(lista\_alcanzables, piedra\_anterior)
		\ELSE
			\IF{($|$piedra\_anterior $-$ v$_i$ $|$ $>$ q)}
				\STATE \COMMENT{asumimos que ``p'' es la cota inferior y ``q'' es la cota superior para mayor claridad}
				\STATE \COMMENT{entonces ==$>$si ya me alejé demasiado, que pase a buscar los alcanzables por derecha}
				\STATE terminé $\leftarrow$ TRUE
			\ENDIF
		\ENDIF
	\IF{(hay una piedra anterior)}
				\STATE piedra\_anterior $\leftarrow$ anterior(piedra\_anterior)
	\ENDIF
	\ENDWHILE
	\STATE terminé $\leftarrow$ FALSE
	\STATE \COMMENT{ahora busco a los alcanzables por derecha}
	\STATE \COMMENT{(es análogo que por izquierda, no es necesario revisarlo detenidamente)}
	\WHILE{((hay una piedra siguiente) y !(terminé))}
		\IF{(es\_alcanzable(piedra\_siguiente, v$_i$))}
			\STATE agregar(lista\_alcanzables, piedra\_siguiente)
		\ELSE
			\IF{$|$piedra\_siguiente $-$ v$_i$ $|$ $>$ q}
				\STATE \COMMENT{asumimos que ``p'' es la cota inferior y ``q'' es la cota superior para mayor claridad}
				\STATE \COMMENT{entonces ==$>$si ya me alejé demasiado, que finalmente agregue la lista definitiva}
				\STATE terminé $\leftarrow$ TRUE
			\ENDIF
		\ENDIF
	\IF{(hay una piedra siguiente)}
			\STATE piedra\_siguiente $\leftarrow$ siguiente(piedra\_siguiente)
	\ENDIF
	\ENDWHILE
	\STATE agregar(tronco, $<$v$_i$, lista\_alcanzables$>$)
\ENDFOR
\STATE return tronco
\end{algorithmic}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{algorithm}[H]
%\caption{\operL{es\_alcanzable}{\vin{x}{posicion}, \vin{y}{posicion}}{boolean}}
%\begin{algorithmic}[1]\parskip=1mm
%\STATE \COMMENT{asumimos que ``p'' es la cota inferior y ``q'' es la cota superior para mayor claridad}
%\IF{($|$X-Y$|$ $<$ p) ó ($|$X-Y$|$ $>$ q)}
%	\STATE return false
%\ELSE
%	\STATE return true
%\ENDIF
%\end{algorithmic}
%\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{parr}

\subsection{Explicación del pseudocódigo}

\begin{compactenum}
	\item Sean:
	\begin{compactitem}
		\item \textbf{v\_p} el vector de posiciones
		\item \textbf{p} y \textbf{q} los enteros propiamente dichos
		\item \textbf{Xs\_e\_Ys} la lista de X's e Y's
 	\end{compactitem}	 
	\item Procesamos a \textbf{v\_p} generando un nuevo vector llamado \textbf{tronco} tal manera que éste contiene elementos de tipo tupla$<$posición, Lista$<$posicion\_vector\_tronco$>>$ sabiendo que:
	\begin{compactitem}
		\item En \textbf{tronco}[i], la parte tupla.\textit{posición} corresponde al número que traía el iésimo elemento del vector de posiciones de la entrada, o sea, \textbf{v\_p}[i], y éste puede ser diferente o no al \textbf{i}.
		\item En cambio, la parte tupla.\textit{alcanzables} es una lista de \textit{i's} del vector \textbf{tronco} y no del vector \textbf{v\_p}. Es decir, cada índice de esta lista corresponde a un elemento del vector (recordar que tronco[i].posición es diferente a i para todo i). De esta forma podemos acceder en tiempo constante a cada una de las piedras alcanzables por cada piedra. O sea, dada una piedra X podemos acceder en tiempo constante  a todas las piedras X$_i$ alcanzables desde X.
 	\end{compactitem}
	\item Luego, hacemos \textit{básicamente} la siguiente llamada recursiva (tronco es el vector formado en el punto anterior):
	\begin{compactitem}
		\item camino(tronco,x,y) = forall(X$_i$ alcanzables desde x) x + camino(tronco,X$_i$,y).
		\item Decimos ``básicamente'' porque en realidad no repetimos buscar caminos desde la misma piedra y al encontrar uno detenemos la ejecución del algoritmo.
		\item Si al recorrer todas las piedras no encuentra un camino entonces devuelve vacío.
		\item Si durante la ejecución encuentra un camino, lo devuelve aunque no necesariamente sea el camino más corto.
	\end{compactitem}
\end{compactenum}

\subsection{Complejidad}
NOTA: tomaremos a \textbf{q} como mayor a \textbf{p} sin perder generalidad (es simplemente un if para fijarse cuál es mayor) y debido a esta decisión tomaremos a p como despreciable en el cálculo de la complejidad (mientras más grande sea p más rápida será la ejecución porque deberá analizar menos piedras el ``existe\_camino'' ya que hay menos piedras alcanzables).
\begin{compactitem}[$\star$]
\item \textbf{es\_alcanzable}: \textbf{O(1)} ya que es un simple \textit{if} y en la guarda de éste s\'olo encontramos una simple comparación entre enteros
\item \textbf{existe\_camino:}
\begin{compactitem}
	\item línea 1: es\_alcanzable lo calculamos en \textbf{O(1)}
	\item líneas 2-3: \textbf{O(1)} ya que son asignaciones simples y el return.
	\item el for entre líneas 5-16:
	\begin{compactitem}[$\circ$]
		 \item se ejecuta, como máximo ``\textbf{2q}'' veces ya que es la máxima cantidad de elementos que puede llegar a alcanzar cada elemento por las restricciones en el salto del sapo (siendo q la máxima distancia que puede saltar el sapo) teniendo, en ese caso, q elementos alcanzables desde la derecha y q elementos alcanzables desde la izquierda.
		 \item línea 6: a la guarda del if la podemos calcular en \textbf{O(1)} teniendo el X$_i$ ya que nos guardamos en el vector 2 booleanos que nos dicen ambas cosas: si lo estamos recorriendo ahora o si ya lo habíamos recorrido y no habíamos encontrado solución.
		 \item línea 7: marcarlo como que lo estoy recorriendo es \textbf{O(1)} ya que es simplemente poner como true al booleano mencionado en el ítem anterior.
		 \item línea 8: es la llamada recursiva. Lo explicaremos al terminar de analizar línea por línea al algoritmo.
		 \item líneas 9-13: \textbf{O(1)} ya que son asignaciones.
	\end{compactitem}
	\item Teniendo en cuenta que el algoritmo no llama recursivamente a elementos repetidos (osea, no repite llamadas recursivas), en peor caso puede llegar a hacer n llamadas recursivas, siendo n la cantidad de piedras de la instancia de entrada.\\
Debido a esta observación podemos afirmar que si se hacen \textbf{n} llamadas a \textbf{existe\_camino} y asumiendo que cada llamada recursiva de la línea 8 se hace en tiempo \textbf{O(1)} (podemos asumir esto porque ya las estaría contando en las n veces que se ejecuta la función) concluímos que la complejidad final de esta función es \textbf{O(q x n)} siendo \textit{q} el \textbf{q} de la entrada.
\end{compactitem}
	\item \textbf{buscar\_alcanzables}:
	\begin{compactitem}
		\item línea 1: \textbf{O(1)} ya que es una simple asignación.
		\item for de las líneas 2-38:
		\begin{compactitem}[$\circ$]
			\item líneas 3-5: \textbf{O(1)} ya que son simples asignaciones.
			\item el while de las línea 6-19:
			\begin{compactitem}[$\circ$]
				\item la guarda en  \textbf{O(1)} ya que mirar si hay una piedra anterior es simplemente mirar si el índice con el que estoy recorriendo el vector es mayor o igual a 0 y mirar el valor de terminé es también constante.
				\item líneas 7-8: \textbf{O(1)} ya que es\_alcanzables es constante y agregar un entero a la lista también
				\item lo que resta del while: es \textbf{O(1)} ya que ejecuta cosas que ya dijimos que eran O(1)
			\end{compactitem}		
			\item el while de las línea 23-36: es análogo al primer while usando las mismas instrucciones pero para el otro lado. \textbf{O(1)}.
		\end{compactitem}
	\item El for de las líneas 2-38 se ejecuta \textbf{n} veces, siendo n la cantidad de piedras de la entrada, y ambos whiles se ejecutan como máximo \textbf{q} veces cada uno, siendo q el de la entrada. La cantidad de repeticiones de los whiles es ésa porque como máximo se alejará \textit{q} elementos del elemento en el que estoy buscando los alcanzables. \\
	Por ende, la complejidad del algoritmo quedaría \textbf{O(2q x n)}$\in$\textbf{O(q x n)}
	\end{compactitem}
	\item \textbf{algoritmo\_ppal}:
	\begin{compactitem}
		\item línea 1: \textbf{O(q x n)}
		\item línea 2: \textbf{O(1)}
		\item línea 3: \textbf{O(q x n)}
		\item resto de las líneas: \textbf{O(1)}
	\end{compactitem}
	Podemos concluir, entonces, que la complejidad del algoritmo es \textbf{O(q x n)}, pero además sabemos que \textit{q} es una constante y la podemos asumir acotada y en especial es despreciable al lado de \textit{n} ya que es menor a \textbf{10}. Por ende, la \textbf{complejidad final} de nuestro algoritmo es \textbf{O(n)}.
\end{compactitem}

\subsection{Correctitud de la soluci\'on}
Ya demostramos que la soluci\'on es conseguida en el tiempo m\'inimo esperado por la cátedra pero todavía nos faltaría demostrar que el algoritmo funciona correctamente. Es decir, nos faltaría demostrar que siempre que hay solución la encuentra y siempre que no haya solución devuelva que no hay solución. \\
Repasando la idea del algoritmo, podremos encontrar una similitud entre éste y los de programación dinámica:
{\pointedenum
\begin{compactenum}
	\item Sean \texttt{X} e \texttt{Y} las piedras a las cuales quiero unir con un camino. Sea \texttt{H} el conjunto de piedras alcanzables por \texttt{X}.  Sea \texttt{X$_i$} alguna piedra perteneciente al conjunto \texttt{H} (si no es vacío). \\
Demostraremos que existe un camino entre \texttt{X} e \texttt{Y} $\iff$ \texttt{H} es no vacío y existe un camino desde algún \texttt{X$_i$} perteneciente a \texttt{H} hacia \texttt{Y}.
	\begin{compactenum}
		\item Primero probamos $\Rightarrow$). O sea, existe un camino entre \texttt{X} e \texttt{Y} $\Rightarrow$ \texttt{H} es no vacío y existe un camino desde algún \texttt{X$_i$} perteneciente a \texttt{H} hacia \texttt{Y}.
		\begin{compactitem}
			\item Si existe un camino entre \texttt{X} e \texttt{Y}, entonces debe haber una primer piedra a la que salte \texttt{X} para empezar el recorrido hacia \texttt{Y}, siendo esta piedra un \texttt{X$_i$} o el mismo \texttt{Y}. Entonces, \texttt{H} es no vacío. 
			\item Además, existe un camino entre esta primer piedra e \texttt{Y} que sería el mismo camino que el de entre \texttt{X} e \texttt{Y}, sacando a \texttt{X} como ``piedra inicial''. Por ende, también existe un camino entre algún \texttt{X$_i$} e \texttt{Y}.
		\end{compactitem}
		\item \texttt{H} es no vacío y existe un camino desde algún \texttt{X$_i$} perteneciente a \texttt{H} hacia \texttt{Y} $\Rightarrow$  existe un camino entre \texttt{X} e \texttt{Y}.
		\begin{compactitem}
			\item Si existe un camino desde algún \texttt{X$_i$} perteneciente a \texttt{H} hacia \texttt{Y}, entonces un camino válido entre \texttt{X} e \texttt{Y} sería el de primero saltar desde \texttt{X} hacia \texttt{X$_i$} y después seguir el camino ya existente.
		\end{compactitem}
	\end{compactenum}
	\item Ahora demostraremos que por lo demostrado en 1, nuestro algoritmo funciona.
		\begin{compactitem}
			\item En casa paso  recursivo del algoritmo buscamos un camino entre los \texttt{X$_i$} e \texttt{Y} y si para algún \texttt{X$_i$} existe, entonces existe para \texttt{X} e \texttt{Y}, aprovech\'andonos de la propiedad demostrada en 1. Con la función \textit{buscar\_alcanzables} encontramos todos los \texttt{X$_i$} para todo \texttt{X} y los recorremos con la función recursiva \textit{existe\_camino}.
			\item Adem\'as podemos demostrar que el algoritmo siempre termina porque nunca hacemos la misma llamada recursiva entre dos mismas piedras y logramos verificar esto haciendo uso de booleanos que recuerdan si ya pas\'e por ah\'i y (por ende no vale la pena seguir ese camino porque ya s\'e que por ah\'i no hay soluciones v\'alidas) o si por alguna razón durante alguna llamada recursiva llegué a la misma llamada recursiva y si la hago de nuevo generaría un loop infinito.
		\end{compactitem}
\end{compactenum}
}



\subsection{Casos de Tests}
\textit{Para los tests de rendimiento contamos las operaciones básicas. Es decir, usamos un contador y cada vez que había una operación que tome tiempo constante sumábamos 1 a este contador y para todas las funciones que tarden O(n) con \textit{n} algun entero, sumábamos n al contador, si sólo si no podemos contar atómicamente las n posiciones de esta operación.}


\begin{compactitem}
	\item \textbf{Test Un Movimiento:} Casos en los que \texttt{Y} sea uno de los \textit{alcanzables} desde \texttt{X} en un salto.
	\begin{compactitem}
		\item En estos casos, predecimos que el tiempo de ejecución va a ser constante si sólo contamos el tiempo de ejecución de \textit{buscar\_camino} y tiempo O(pn), con \textit{p} el de la entrada, si contamos la ejecución de todo el algoritmo.
	\end{compactitem}
	\item \textbf{Test Primero Con Último:} Casos en los que \texttt{X} esté en una punta del tronco e \texttt{Y} en la otra y además sólo pueda acercarse a \texttt{Y} una piedra por vez.
	\begin{compactitem}
		\item En estos casos, predecimos que el tiempo de ejecución va a ser  O(pn), con \textit{p} el de la entrada, si contamos la ejecución de todo el algoritmo. Además, el tiempo de buscar camino será ahora O(pn) también ya que ahora sí tiene que recorrer todo el vector en todos los casos y en peor caso en particular.
	\end{compactitem}
%	\item Casos en los que \texttt{X} tenga que alejarse antes de acercarse durante el recorrido de alguna piedra.
%	\begin{compactitem}
%		\item 
%	\end{compactitem}
\end{compactitem}

\subsection{Gráficos}
NOTA: consideramos como tamaño de entrada al tamaño del vector ya que el tamañ del resto de las variables de entrada (\textit{p},\textit{q}, \textit{X} e \textit{Y}) no varían entre instancias.


\begin{figure}[H]
\centering
\epsfig{file=./graficos/test2-ej3-PrimeroConUltimo-png.pdf,width=0.7\linewidth,clip=}
\caption{Resultado Test Rendimiento Primero con Último}
\label{fig:sin-repet}
\end{figure}
En nuestro primer gráfico, analizaremos el rendimiento de todo el algoritmo ejecutando el test ``Primero con último'' y podemos notar que es posible acotar el crecimiento del tiempo del algoritmo con una función lineal. En este caso en particular con la función \texttt{110*x +300}. Aunque parezcan constantes algo grandes, debemos tomar en cuenta que podía llegar a tardar O(10 * n) a primera vista dependiendo en los valores de las variables \textit{p} y \textit{q} y a esto además sumarle las iteraciones otras iteraciones del vector que despreciamos ya que evalúamos por complejidad asintótica y O(an) $\in$ O(n), con a constante.

\begin{figure}[H]
\centering
\epsfig{file=./graficos/test1-ej3-UnMov-png.pdf,width=0.7\linewidth,clip=}
\caption{Resultado Test Rendimiento Un Movimiento}
\label{fig:sin-repet}
\end{figure}
En nuestro segundo gráfico, ahora nos toca analizar el rendimiento del algoritmo ejecutando el test ``Un Movimiento'' y también afirmaremos que es posible acotar el tiempo transcurrido por el algoritmo con una función lineal, aunque ahora la función en particular sería \texttt{90*x +100}. Lo de constantes algo grandes se sigue aplicando, aunque si miramos con más detenimiento, podemos notar que en este test el algoritmo tardo \textit{un poco} menos que el anterior.

\begin{figure}[H]
\centering
\epsfig{file=./graficos/test3-ej3-ambos-png.pdf,width=0.7\linewidth,clip=}
\caption{Resultado Test Rendimiento Ambos}
\label{fig:sin-repet}
\end{figure}

Después de analizarlos a ambos en un mismo gráfico, descubrimos que la diferencia, que aunque pequeña, se va intensificando con valores más grandes y esto se debe a que en el caso de \textbf{Un Movimiento} la función \textit{existe\_camino} es de tiempo constante ya que pregunta si X es alcanzable por Y en un salto y al percatarse de ello no tiene que meterse a buscar un sub-camino que tendría que recorrer potencialmente el vector entero. En cambio, en el test \textbf{Primero con Último}, ésa misma función (\textit{existe\_camino}) debe iterar a \textbf{todas} las piedras del vector. Aunque ambas funciones son similares, esto marcaría la diferencia entre la constante que está multiplicando al \textbf{n} en la complejidad de ambas.


\begin{figure}[H]
\centering
\epsfig{file=./graficos/test3-ej3-ambos-solo-existe-camino-png.pdf,width=0.7\linewidth,clip=}
\caption{Resultado Test Rendimiento Ambos pero sólo de existe\_camino}
\label{fig:sin-repet}
\end{figure}
En este \'ultimo gr\'afico, es clara la diferencia entre el crecimiento de uno y de otro, siendo el test \textit{Un Movimiento} de duraci\'on constante y el test \textit{Primero con \'ultimo}, informalmente dicho, \textit{algo} lineal.


\subsection{Conclusiones}
Nuestro primer enfoque fue pensar en generar una matriz o, mejor aún, un arreglo con las mismas posiciones del vector de entrada, aunque esto hubiera llevado a la complejidad a ser igual al máximo tronco[i] para todo i. \\
Después de razonarlo un poco, nos dimos cuenta que no era necesario y con un simple ``re-enfoque'' podríamos seguir obteniendo información vital en tiempo constante al guardarnos el índice de las posiciones en vez de las posiciones en sí. \\
En conclusión, aprendimos que la primer solución pensada no siempre es la mejor y que tomándose el tiempo necesario para pensar la misma, puede resultar mas simple.



